This invention is in the field of non-volatile memory, and is more specifically directed to error correction coding in non-volatile solid-state memory devices of the flash type.
As well known in the art, “flash” memories are electrically-erasable semiconductor memory devices that can be erased and rewritten in relatively small blocks, rather than on a chip-wide or large-block basis as in previous electrically-erasable programmable read-only memory (EEPROM) devices. As such, flash memory has become especially popular for applications in which non-volatility (i.e., data retention after removal of power) of the stored data is essential, but in which the frequency of rewriting is relatively low. Examples of popular applications of flash memory include portable audio players, “SIM” card storage of telephone numbers and phone activity in cellular telephone handsets, “thumbkey” removable storage devices for computers and workstations, storage devices for digital cameras, and the like.
There are many commercially successful non-volatile memory products being used today, particularly in the form of small form factor cards that include one or more integrated circuit chips to realize a flash EEPROM memory array. A memory controller, usually but not necessarily on a separate integrated circuit chip from the memory array, interfaces with a host to which the card is removably connected and controls operation of the memory array within the card. Such a controller typically includes a microprocessor, some non-volatile read-only-memory (ROM), a volatile random-access-memory (RAM), and one or more special circuits, such as an encoder and decoder for implementing an error-correction-code (ECC) on data passing through the controller during the programming and reading of data into and from the memory. Modem and commercially available flash memory cards include COMPACTFLASH (CF) cards, MULTIMEDIA cards (MMC), SECURE DIGITAL (SD) cards, personnel tags (P-Tag), and MEMORY STICK cards. Conventional host systems that can utilize such flash memory cards include personal computers, notebook computers, personal digital assistants (PDAs), various data communication devices, digital cameras, cellular telephones, portable audio players, automobile sound systems, and similar types of equipment. The removable flash memory card in some systems does not include a controller, in which case the host itself controls operation of the memory array in the card. Examples of this type of memory system include SMART MEDIA cards and xD cards. According to these two classes of memory cards, control of the memory array may be achieved by software on a controller in the card, or by control software in the host for those cards that do not have a controller function. In addition, besides the memory card implementation, this type of memory can alternatively be embedded directly into host systems, of various types. In both the removable and embedded applications, host data is stored in the memory array according to a storage scheme implemented by memory control software.
An important recent advance in semiconductor non-volatile memory technology is the arrangement of the flash memory cells as “NAND” memory rather than as “NOR” memory. As known in the art, NOR flash memory refers to the conventional arrangement of a column of memory cells in parallel between a bit line and a source line. Access of a specific cell in a NOR column is made by driving its word line (control gate) active while holding the other cells in the column off, so that the current between the bit line and source line is determined by the state of the accessed cell. Memory cells in a column of NAND memory, on the other hand, are connected in series between the bit line and the source line. Accessing of a specific cell in a NAND column thus requires turning on all of the cells in the column with active word line levels, and applying an intermediate word line level to the cell to be accessed, such that the current between the bit line and source line is, again, determined by the state of the accessed cell. As well known in the art, the chip area required per bit of NAND flash memory is much reduced from the area per bit of NOR flash memory, primarily because fewer conductors (and therefore contacts) are required for a column of NAND memory relative to NOR memory; in addition, access transistors can be shared among a large number of cells in the NAND arrangement. Additionally, conventional NAND flash memory is conveniently accessed serially, for example by sequentially accessing cells along the columns, rather than as a random access memory as in the case of NOR memory. NAND memory is thus especially well-suited for music and video storage applications
Another important recent advance in the field of flash memory is referred to in the art as the multilevel program cell (MLC). According to this approach, more than two data states are made possible for each memory cell, simply by more finely controlling the programming of the cell. In conventional binary data storage, each memory cell is programmed into either a “0” or a “1” state. Reading of such binary cells is accomplished by applying a single control voltage to the control gate of the addressed memory cell so that the transistor conducts if programmed to a “1” state, but remains off in the “0” state; sensing of the conduction through the addressed memory cell thus returns the programmed state of the cell. In contrast, according to a typical example of the MLC approach, four possible states are defined for each memory cell, typically corresponding to binary values 00, 01, 10, 11. In effect, the two intermediate states correspond to two levels of partial programming of the cell between the fully erased and fully programmed states. Some implementations of MLC flash memory with up to eight possible states, or three binary bits, per cell are known. The ability to store two or three bits of data on each memory cell immediately doubles or triples the data capacity of a flash memory chip. Examples of MLC flash memory cells and memories including such MLC cells are described in U.S. Pat. No. 5,172,338, and U.S. Pat. No. 6,747,892 B2, both commonly assigned herewith and incorporated herein by this reference.
The combination of MLC technology with the efficiencies of NAND flash memory architectures has resulted in significantly reduced cost per bit for semiconductor non-volatile storage, as well as improved system reliability, and a higher data capacity and system functionality for a given form factor.
Modem flash memory devices, particularly those of the NAND architecture and involving MLC cells, are arranged in “blocks” and “pages”. A block refers to an erase unit, and defines a group of cells that are simultaneously erased in a single erase operation. Typically, a block of cells is smallest group of cells that can be erased. A page refers to a programming unit, and defines a group of cells that are simultaneously programmed, or written, in a single programming operation. Each block typically includes multiple pages. Generally, the arrangement of cells into pages and blocks is based on the physical realization of the memory array. For example, in many NAND memory arrays, a page of memory cells is defined by those cells that share the same word line, and a block is defined by those pages residing in the same “NAND” chain. For example, if a NAND chain includes thirty-two memory cells in series, a block will include thirty-two pages.
Historically, the organization of data stored in a flash memory has followed the file systems used in connection with magnetic disk storage, and as such is based on “sectors”. A sector is typically a group of data of a fixed size, for example, 512 bytes of user data plus some number of bytes of overhead. In many modern file systems, the operating system of the computer or other host system arranges data into sectors, and writes data to and reads data from non-volatile storage on a sector-by-sector basis. To permit convenient use of flash memory devices as non-volatile storage devices in such systems and applications, many modern flash memories handle data in a similar fashion, mapping logical “sector” addresses to physical addresses in the flash memory array.
In recent years, the sizes and capacities of flash memory devices have greatly increased, resulting in memory arrays of more than 1 million cells. In such arrays, a single word line may extend to over 2000 memory cells, placing that many memory cells within the same page, or programming unit. In such large scale flash memories, therefore, each page now includes multiple sectors. As such, the host system will be communicating units of data to the flash memory that are smaller than the smallest programming unit in the device.
Conventional flash memories have handled the writing of sectors within a page by way of “partial page programming”. To perform programming of a partial page, for example in programming one of four sectors within a page, the word line for the page receives the high programming voltage, but only those memory cells on that word line within the sector being programmed (and, of course, those memory cells within that sector that are to receive a programmed data state) receive source and drain voltages (via the bit lines and the other cells in the NAND chain) that enable programming. As such, individual sectors may be separately written into the same page.
However, as device geometries continue to shrink in order to realize more memory capacity within a flash memory device, the reliability of the floating-gate transistors of the memory cells becomes more fragile. And it has been observed that the driving of programming voltages onto the word line, or control gate of the floating-gate transistor, tends to stress those transistors that are not being programmed. For example, in a page having four sectors, and in which each sector is individually written, each cell will receive three additional programming cycles beyond that of its own sector, and will thus receive four times the stress that it would have received from only a single programming cycle. As such, it is contemplated that modern flash memory devices will prohibit partial page programming, to preserve the reliability of the device. Under this constraint, flash memory devices or memory controllers will buffer the data for individual sectors until all sectors in the page can be programmed in the same programming operation.
By way of further background, the use of error correction coding (ECC) in mass data storage devices and storage systems, as well as in data communications systems, is well known. As fundamental in this art, error correction coding involves the storage or communication of additional bits (commonly referred to as parity bits, code bits, checksum, etc.) that are determined or calculated based on the data bits being encoded. For example, in the case of ECC for data storage, the actual data is used in encoding a code word that has more bits than the actual data itself. To retrieval the stored data, the stored code word is decoded according to the same code as used to encode the code word. Because the code bits “over-specify” the actual data portion of the code word, some number of errored bits can be tolerated, without any loss of actual data evident after decoding.
Many coding schemes for ECC are well known in the art. These conventional error correction codes are especially useful in large scale memories, including flash memories, because of the substantial impact on manufacturing yield and device reliability that such coding schemes can provide, rendering devices that have a few non-programmable or defective cells as useable. Of course, a tradeoff exists between the yield savings and the cost of providing additional memory cells to store the code bits (i.e., the code “rate”). As such, some ECC codes are better suited for flash memory devices than others; generally, ECC codes for flash memory devices tend to have higher code rates (i.e., a lower ratio of code bits to data bits) than the codes used in data communications applications (which may have code rates as low as ½). Examples of well-known ECC codes commonly used in connection with flash memory storage include Reed-Solomon codes, other BCH codes, Hamming codes, and the like. Typically, the error correction codes used in connection with flash memory storage are “systematic”, in that the data portion of the eventual code word is unchanged from the actual data being encoded, with the code or parity bits appended to the data bits to form the complete code word.
By way of further background, FIG. 1 illustrates the arrangement of actual data (“payload” data) and code bits in multi-sector page 8 of a conventional flash memory device. As shown in FIG. 1, page 8 includes four sectors 100 through 101, each of which includes a data portion 11, ECC bit portion 12, and header 13. Data portion 11 typically occupies the majority of the cells in a given sector 10; for example, a typical sector 10 of 528 bytes will include 512 bytes as data portion 11, and another sixteen bytes for ECC bit portion 12 and header 13. And as illustrated in FIG. 1, the data portions 11 of the various sectors 10 within a given page 8 may store different types of data. In page 8 of FIG. 1, data portions 11 of sectors 100, 101, 102 store “user” data, which is data generated by an application or user of the system including the non-volatile memory containing page 8. Data portion 11 of sector 103 stores “control” data, such control data including information useful in the operation of the non-volatile memory, such as address tables for logical-to-physical address mapping, erase counts, status information, and the like. The control data in data portion 11 of sector 103 may or may not pertain to the user data in data portions 11 of sectors 100 through 103, and may or may not be synchronous in time with that user data (i.e., it may have been written at a substantially different time from the user data). Header portions 13 for each sector 100 through 103 stores control information for its sector, such control information including identifying information for its associated sector, and status information regarding the data in its associated data portion 11.
As mentioned above, the operating system that controls the writing and reading of data to and from the memory containing page 8 arranges the data in the form of sectors, analogous (or identical) to the arrangement of data as stored on a magnetic disk drive. As such, if a large amount of data is to be written to non-volatile memory, that data is grouped into sectors (e.g., 512 bytes), and presented to the memory controller or other logic for effecting the write of that data to the non-volatile memory. A controller or other logic for the flash memory containing page 8 of FIG. 1 uses the payload data (user or control) for a given sector to calculate the ECC bits for that sector. In other words, the ECC bits for a sector depend only on the data for that sector, and not on the data contents in any other sector of the page. The number of ECC bits generated for a code word of a given size depends on the particular code being used and, of course, on the length of the data block being encoded. Upon the writing of the data to data portion 11 of a selected sector 10, the calculated ECC bits are written to ECC bit portion 12 for that sector, along with the appropriate header data written to header portion 13. And, upon reading of a sector of data from data portion 11 of a selected sector, the contents of the ECC bit portion 12 for that sector is also read, and is used to detect (and possibly correct) errors in the data retrieved from that data portion 11.
As noted above, the number of code bits generated by conventional ECC codes depends on the number of bits in the data being encoded. One can consider the “efficiency” of a code by considering the ratio of the additional code bits to the number of data bits being encoded; another known measure of this efficiency is the “code rate”, which is the ratio of the number of data bits to the total bits (code bits plus data bits). By way of further background, it is known that conventional ECC codes, such as Reed-Solomon and BCH coding, tend to be more efficient when encoding larger code blocks.